1. Field of the Invention
The present invention relates to a flow controlling apparatus provided in a node that accesses a packet routing network such as the Internet, the flow controlling apparatus performing a rate-based congestion control on packets that are supplied from a terminal accommodated in the node or via an incoming line as well as performing buffer management on buffers corresponding to the respective classes of such packets. The invention also relates to a node apparatus that incorporates such a flow controlling apparatus.
2. Description of the Related Art
In the Internet which has spread rapidly in recent years, best effort type services which do not assure any transmission delay time or transmission band are being provided to many users.
Further, in the Internet, attempts are being made positively to realize speech communication services using VoIP (voice over IP), for example, and to utilize the Internet as a virtual private networks (VPN).
Therefore, for example, techniques for assuring, end to end, the following service classes that conform to various service forms as shown in FIG. 8 are being applied to the Internet:                A DS (delay sensitive) type service class (hereinafter referred to merely as “DS class”) in which both of a transmission bandwidth and a transmission delay time are assured by discarding packets that are supplied at a rate beyond the transmission bandwidth.        A TS (throughput sensitive) type service class (hereinafter referred to merely as “TS class”) in which a prescribed, minimum transmission bandwidth is assured and an excess bandwidth is assigned as appropriate.        A BE (best effort) type service (hereinafter referred to merely as “BE class”) in which a service is provided as long as an excess bandwidth exists and none of a transmission bandwidth, a transmission delay time, and transmission quality are assured.        
FIG. 9 shows the configuration of an example apparatus that performs a flow control for the incoming line of a node.
As shown in FIG. 9, a sequence of packets that are sent from a terminal accommodated in the local station (or packets received from a preceding transmission section) is supplied to the input of a band monitoring part 51. The output of the band monitoring part 51 is directly connected to the input of a congestion controlling part 52. The congestion controlling part 52 has outputs corresponding to respective service classes (for simplicity, it is assumed here that they are the above-described DS (delay sensitive) type, TS (throughput sensitive) type, and BE (best effort) type service classes) to which the packets may belong. The outputs of the congestion controlling part 52 are directly connected to the inputs of queues 53-1 to 53-3 that correspond to the respective service classes. The outputs of the queues 53-1 to 53-3 are connected to respective ports of a packet switch (not shown; or a line interfacing part). The control terminals of a scheduler 54 that plays a leading role in reading (first-in first-out) of the queues 53-1 to 53-3 are directly connected to the read control terminals of the queues 53-1 to 53-3, respectively.
In the conventional example having the above configuration, the band monitoring part 51 is informed in advance of a transmission bandwidth (hereinafter referred to as “contracted bandwidth”) that the user of the above-mentioned terminal, for example, requested at the time of contract. Every time receiving a packet (hereinafter referred to “new packet”) from each terminal, the band monitoring part 51 performs a rate-based congestion control (mean policing) by performing the following series of operations:
(1) Identifies a flow (including the identifier of a sender) to which the new packet belongs by referring to a prescribed field of the new packet.
(2) Acquires a contracted bandwidth of the sender terminal.
(3) Judges, according to a prescribed algorithm such as the leaky bucket algorithm, whether the rate (average rate) of packets belonging to the identified flow exceeds the contracted bandwidth.
(4) Discards the new packet if the judgment result is true.
(5) Passes the new packet to the congestion controlling part 52 when the judgment result is false.
In a process of the above rate-based congestion control, in practice, the above judgment is done in consideration of not only the above-mentioned contracted bandwidth but also the statuses (including the degree of congestion) of the network and the destination of the new packet. However, those statuses are not important features of the invention, they will not be described in detail.
Every time receiving a new packet from the band monitoring part 51, the congestion controlling part 52 performs the following processing according to the RED (random early discard) algorithm or the WRD (weighted random early discard) algorithm:
(1) Identifies a service class to which the new packet belongs by referring to a prescribed field of the packet.
(2) Judges whether the amount of information (may be a queue length or an average value of queue lengths) of packets stored in the queue (hereinafter referred to as “subject queue”) corresponding to the thus-identified service class among the queues 53-1 to 53-3 exceeds a prescribed upper limit value THmin (indicated by symbol (1) in FIG. 10).
(3) Stores the new packet in the subject queue according to first-in first-out (indicated by symbol (2) in FIG. 10) when the judgment result is false.
(4) Discards the new packet randomly at a probability that is higher when the amount of information is larger (indicated by symbol (3) in FIG. 10) when the judgment result is true.
The transmission bandwidth of the DS class and the minimum bandwidth of the TS class are bandwidths that should be assured within the sizes of the corresponding queues of the queues 53-1 to 53-3. Therefore, the service class of a packet that can be discarded by the congestion controlling part 52 during the course of the above processing is limited to the TS class and the BE class having an excess transmission bandwidth that can be allotted to the packet.
In a process that packets stored in advance in the queues 53-1 to 53-3 are read out under scheduling that is performed by the scheduler 54, prescribed processing is performed through cooperation between the scheduler 54 and the queues 53-1 to 53-3.
However, the procedure of such processing is not an important feature of the invention, it will not be described any further.
New packets are captured by the band monitoring part 51 within the contracted bandwidth. Then, the new packets are stored sequentially in the queue corresponding to the service class to which the packets belong among the queues 53-1 to 53-3 unless packets of an excessive amount of information (number) are stored in the queue, and read out sequentially under prescribed buffer management.
Therefore, in a node to which the conventional example is applied, occurrence of a deadlock is avoided under the above rate-based congestion control and buffer management, the flow control is performed stably, and the utilization efficiency of the network is kept high.
Incidentally, in the above conventional example, packets to be discarded by the congestion controlling part 52 are selected randomly according to the above-described algorithm and a flow to which each packet belongs is not identified during the course of the selection.
Therefore, in a period when many flows are formed by a sequence of packets belonging to one of the TS class and the BE class, the probabilities that packets belonging to the respective flows are discarded are not necessarily the same. Among packets belong to the same service class, packets belonging to a particular flow may be discarded at a higher probability than packets belonging to other flows.